Power Programmierung 2/Power-Programmierung CD 2 (Tewi)(1994).iso/c/library/dos/genetk/read.me

Text File | 1993-06-28 | 10.0 KB | 235 lines

 (c) Copyright 1993 Toms Computer Solutions, Inc. All rights reserved.







--------------------- Genetic Algorithms------------------------------------



 Genetic algorithms can be used to solve a large class of
problems. The general approach is that a population of random
solutions is generated. Each element of this population is given
a score. A higher score indicates a better solution. Some of the
solutions with lower scores are dropped from the population.
They are replaced by new solutions that are created by mating.
Mating is the process of combining properties from a pair of the
more successful, higher scoring, elements (the parents)
resulting in a new element (the offspring).



Randomly selected elements of the population are subjected to
mutation or random changes to their properties. Just as mating
causes new combinations of properties, mutation causes new
properties to be introduced that were not previously found in
the population.

This process of introducing new properties and combinations of
properties, along with the removal of the less successful
elements results in the evolution of more successful solutions.
This process can be repeated for many generations until a
satisfactory solution is evolved.



Does it work? The fact that you are intelligent enough to read
this would indicate that in fact it does work! The process
described above is very similar to biological genetics, natural
selection and evolution that have resulted in yourself and all
other forms of life on Earth. Genetic Algorithms have been
referred to as "God's Algorithms".



Whether or not you agree with this, you may find that genetic
algorithms are a useful tool for optimizing parameters and
solving other problems.



------- Problems that can be Solved with Genetic
Algorithms-----------------



 In order for a problem to be solved on a computer with a
genetic algorithm it must meet two criteria.



First it must be possible to represent a solution to the problem
in a series of binary bits. This is not a difficult criterion
since text, integers and floating point numbers can all be
represented as series of binary bits. Computer programs and data
files can be represented as a series of binary bits. Even things
like colors, graphic images, and equations can be represented as
a series of binary bits. It could be argued that, with fuzzy
logic, properties like hot, warm, cold, pretty, nice, good and
bad, could all be represented as a series of binary strings.



The second criterion is more difficult. For the genetic
algorithm to work it must be possible to create a scoring
function that will return a score when it is passed a series of
binary bits that represent a solution. This means that a problem
like the Traveling Salesman Problem could be worked on because a
function that returns a score could be easily written. The score
would be based on the total distance that the salesman had to
travel. A problem like "What strategy is good for buying and
selling Municipal Bonds or Deutsche Mark futures?"  could also
be worked on with a score based on how much money was made or
lost with a given strategy. There are some problems for which it
would be difficult to write such a scoring function. Solutions
to the problem of "What is a good philosophy of life?" could
possibly be represented as series of binary bits in a large text
file (or possibly a short text file) but it would be difficult
to create a function that would score the different philosophies.



Other issues are also important for practical use of genetic
algorithms. The time required to run the scoring function is
very important. For example if you are trying to evolve a
solution for "What is a good strategy for playing chess?" you
might create a scoring function that requires that an entire
game of chess be played. if this scoring function takes an hour
to run and your population has 500 elements, then it would take
more than 20 days to score each generation of your population.
It might well take thousands or more generations meaning that
the evolution of a good solution might take many human
lifetimes. Always try to optimize the scoring function to run as
fast as possible. Also run Genetic algorithms on the fastest
machines possible. You may find that one good use of genetic
algorithms is that they can be used to justify the purchase of
the latest and fastest computer! Genetic algorithms are very
well suited to multiprocessor machines or even massively
parallel systems.



Another important issue for use of genetic algorithms is the
selection of the scoring function. The scoring functions should
reflect small improvements in the solutions. Otherwise the
evolution will be very slow. For example  you could score a
chess playing algorithm with a one for wins and a zero for
losses. The problem with this is that a genetic algorithm will
have no way of knowing whether a  subtle change in the strategy
was good or bad. A different scoring algorithm that gave points
at the end of the game, for the ratio of black to white pieces
and gave points for the number of turns it took to win or lose,
combined with a large number of points for actually winning
might be better. In this case a slightly better strategy could
be recognized and that line of evolution encouraged by the
genetic algorithm. A good example of this is the first demo
program, STRDEMO.BAT. Here the genetic algorithm attempts to
find the solution string "Genetic algorithm at work!". One
scoring function could be to simply add a minus one for every
wrong letter. A better scoring algorithm is based on how wrong
the letter is. For example if the target letter is a "C", then
an "A" would be scored as a minus two, and a "B" would be scored
as a minus one and "C" would be scored as a zero. This gives the
genetic algorithm more information than just minus one for each
wrong letter. It allows it to improve gradually on the solution
string. It could be argued that the STRDEMO is a very contrived
problem since the scoring algorithm knows what the target string
is and creates a score by directly comparing it with the genetic
solutions. I have used it anyway because it is a simple example
that the reader may want to use to develop their own problems
for the genetic algorithm to solve.



The second example is not so contrived. CITYDEMO is an example
of the genetic algorithm being used to solve the famous
traveling salesperson problem. The problem itself is simple. A
salesperson needs to travel to n cities and then return to  his
or her own home town. He or she must go to each and every city
once and only once. The problem is to determine the route that
will minimize the total travel distance. (Another problem is to
maximize the total distance. Presumably his company is paying
the expenses, and the salesperson is trying to get enough
frequent flier miles to take his family to Hawaii!) It is
generally believed (but not proven) that the only way to find
the absolute shortest path is through an exhaustive search of
all routes. This becomes unfeasible as the number of cities
increases. Here the genetic algorithm comes up with
progressively better solutions. It may eventually come up with
the best possible solution but this is not certain. Hopefully an
acceptable solution should eventually evolve. CITYDEMO will take
a lot longer to run than STRDEMO. The early solutions are not
likely to be good, but after an hour or two the genetic
algorithm should evolve a solution that is better. Unfortunately
the evolution process seems to be fast at first when it is easy
to improve on bad solutions. Later as the solutions improve the
algorithm appears to slow down. Readers with lots of patience
may want to leave their machines running overnight to achieve
better solutions. Even after the solution seems to be stabilized
leaving the system running for a couple of days (with the
cooperation of your local power company) may result in further
improvement.



The third example FINDEMO is not included with this version and
is only provided to users who send me the $39 registration fee.
(Hey, my kids have to eat!)  It uses the genetic algorithm to
evolve a system of buy and sell signals for financial
instruments like stocks, bonds and commodities. The user
provides the system with files of information about the previous
performance of the instrument. The system then evolves a trading
system based on the historical data. Of course there are no
guarantees of future success but in fact the results with  paper
trading have been extremely interesting. This is a very
interesting example of the use of genetic algorithms, because
the problem itself may not be well defined but it can be scored
easily. The score is simply how much money the system wins or
loses. It is also interesting because it is an example of a
problem that is constantly changing. A good investment strategy
for one year may not work in another year. These types of
problems are often good candidates for solution with genetic
algorithms. In the same way that changes in the physical
environment may cause different organisms to evolve, changes in
the financial environment will cause different investment
strategies to evolve.







 Users can send the $39 registration fee to:



Tom's Computer Solutions, Inc.
21585 Toledo Road
Boca Raton FL. 33433



Be sure to send me your name and address, so I can send you the
FINDEMO example with complete documentation and a graphing
program which will graph the results of the FINDEMO example. I
will also include the source code GENETIC.CPP which is used to
create GENETIC.OBJ, and additional documentation of the
GENPARMS.TXT file.



If you have any problems, questions or interesting comments
about this package please leave me a message on America On Line.
My name is Tom Fernandez and my user ID is IMProgramr. It is my
intention to support this package, so I will be very grateful to
anyone who finds any problems or has suggestions on how the
system can be improved.